package org.datrie;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Node {
	public String tail;
	public Character data;
	public boolean split = false;
	public Integer id;
	public Node parent;
	public Integer tailp;
	public List<Node> children = new ArrayList<Node>(0);
	public Integer base;
	public static List<Integer> occupiedIds = new ArrayList<Integer>();
	private static List<Integer> occupiedBases = new ArrayList<Integer>();

	public boolean isLeaf() {
		return children.isEmpty();
	}

	public boolean hasSiblings() {
		if (parent == null)
			return false;
		return parent.children.size() > 1;
	}

	public boolean isRoot() {
		return parent == null;
	}

	/**
	 * Un nodo es reducible sii cumple una de las siguientes condiciones<br>
	 * - Tiene 2 hijos tales que todos sus nodos descendientes son padres de
	 * hasta un hijo<br>
	 * - Tiene 1 hijo tal que en toda su descendencia solo un nodo tiene dos
	 * hijos, y el resto tiene hasta uno
	 * 
	 * @return
	 */
	public boolean isReducible() {
		if (isRoot() || isLeaf())
			return false;
		if (children.size() == 1) {
			Node firstPluriparent = getFirstPluriparent();
			if (firstPluriparent.children.size() > 2)
				return false;
			return firstPluriparent.children.get(0).getFirstPluriparent() == null
					&& firstPluriparent.children.get(1).getFirstPluriparent() == null && allLeavesHaveTail();
		} else if (children.size() == 2) {
			return children.get(0).getFirstPluriparent() == null && children.get(1).getFirstPluriparent() == null
					&& allLeavesHaveTail();
		} else
			return false;
	}

	/**
	 * Devuelve true sii todas las hojas que parten de este nodo tienen tail
	 * 
	 * @return
	 */
	private boolean allLeavesHaveTail() {
		if (isLeaf())
			return tail != null && tail.length() > 0;
		else
			for (Node child : children)
				if (!child.allLeavesHaveTail())
					return false;
		return true;
	}

	/**
	 * Busca en la cadena de descendencia de this, el primer nodo que tenga mas
	 * de un hijo y lo devuelve. Puede ser this.
	 * 
	 * @return
	 */
	private Node getFirstPluriparent() {
		Node current = this;
		while (current.children.size() == 1)
			current = current.children.get(0);
		if (current.isLeaf())
			return null;
		else
			return current;
	}

	public void reduce() {
		String prefix = "#";
		Node firstPluriParent = getFirstPluriparent();
		Node current = firstPluriParent;
		while (current != this) {
			prefix = current.data + prefix;
			current = current.parent;
		}
		String suffix1 = getSuffix(firstPluriParent, 0);
		String suffix2 = getSuffix(firstPluriParent, 1);
		tail = prefix + ((char) suffix1.length()) + suffix1 + suffix2 + "#";
		children.clear();
		split = true;
	}

	private String getSuffix(Node firstPluriParent, int index) {
		Node current;
		String suffix = "";
		current = firstPluriParent.children.get(index);
		while (!current.isLeaf()) {
			suffix += current.data;
			current = current.children.get(0);
		}
		suffix += current.data + current.tail.substring(0, current.tail.length() - 1);
		return suffix;
	}

	public void setBase() {
		int i;
		if (occupiedBases.size() < 500)
			i = -1;
		else
			i = Math.max(Collections.max(occupiedBases) - 500, -1);
		while (true) {
			int[] someFreeBases = getFreeBases(i);
			for (Integer baseCandidate : someFreeBases) {
				for (Node child : children)
					if (occupiedIds.contains(baseCandidate + Datrie.alphabet.indexOf(child.data))) {
						baseCandidate = null;
						break;
					}
				if (baseCandidate != null) {
					base = baseCandidate;
					System.out.println("Set base: " + base);
					occupiedBases.add(base);
					for (Node child : children) {
						child.id = base + Datrie.alphabet.indexOf(child.data);
						occupiedIds.add(child.id);
					}
					break;
				}
			}
			if (base == null) {
				i = someFreeBases[someFreeBases.length - 1];
				System.out.println("FreeBase retry...");
			} else
				break;
		}
	}

	private int[] getFreeBases(int i) {
		int n = 0;
		int[] result = new int[300];
		for (int k = i + 1; n < 300; k++)
			if (!occupiedBases.contains(k))
				result[n++] = k;
		return result;
	}

	public int size() {
		if (isLeaf())
			return 0;
		else {
			int size = 1;
			for (Node child : children)
				size += child.size();
			return size;
		}

	}
}
